package demo;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 *    二叉树的中序遍历
 */
class Solution31 {
	public List<Integer> preOrderTraversal(TreeNode root) {
		List<Integer> result = new ArrayList<>();
		Stack<TreeNode> stack = new Stack<>();
		TreeNode node = root;
		while(node != null || !stack.isEmpty()) {
			while(node != null) {
				result.add(node.val);
				stack.push(node);
				node = node.left;
			}
			if (!stack.isEmpty()) {
				node = stack.pop();
				node = node.right;
			}
		}
		return result;
	}
	public List<Integer> midOrderTraversal(TreeNode root) {
		List<Integer> result = new ArrayList<>();
		Stack<TreeNode> stack = new Stack<>();
		TreeNode node = root;
		while (node != null || !stack.isEmpty()) {
			while(node != null) {
				stack.push(node);
				node = node.left;
			}
			if (!stack.isEmpty()) {
				node = stack.pop();
				result.add(node.val);
				node = node.right;
			}
		}
		return result;
	}
	public List<Integer> postOrderTraversal(TreeNode root) {
		List<Integer> result = new ArrayList<>();
		Stack<TreeNode> stack = new Stack<>();
		TreeNode node = root;
		TreeNode lastVisit = root;
		while(node != null || !stack.isEmpty()) {
			while (node != null) {
				stack.push(node);
				node = node.left;
			}
			node = stack.peek();
			if (node.right == null || node.right == lastVisit) {
				result.add(node.val);
				stack.pop();
				lastVisit = node;
				node = null;
			} else {
				node = node.right;
			}
		}
		return result;
	}
}

